function [data_out] = XFFT_4(data_in)
%基4-FFT
%   Detailed explanation goes here
    %% 数组补零
    N = length(data_in);
    N_bit = ceil(log2(N)/log2(4));
    N_ceil = 4^N_bit;
    if(N<N_ceil)
        fft_in = [data_in,zeros(1,N_ceil-N)];
    else
        fft_in = data_in;
    end
    %% 序列倒序
    fft_data = zeros(1,N_ceil);
    %方法1:简单的位操作
    for K=0:N_ceil-1
        bin2 = flip(dec2bin(K,2*N_bit));
        bin2r = bin2;
        for W=1:N_bit
            bin2r(2*W) = bin2(2*W-1);
            bin2r(2*W-1) = bin2(2*W);
        end
        fft_data(K+1) = fft_in(bin2dec(bin2r)+1);
    end
    %% 基4旋转因子
    Base_2 = 4;
    matrix1 = zeros(Base_2,Base_2);
    for K = 1:Base_2
        for L = 1:Base_2
            m = mod((K-1)*(L-1),Base_2);
            matrix1(K,L) = W_mN(m,Base_2);
        end
    end
    %%
    xfft_r1 = zeros(1,N_ceil);
    for series = 0:N_bit-1
        %蝶形运算矩阵
        [ADD] = matrix_add4(N_bit,series);
        ADD(1:4,:) = ADD(1:4,:)+1;
        if(series==0)
            xfft_r = fft_data;
        else
            xfft_r = xfft_r1;
        end
        %矩阵计算
        for M=1:length(ADD(1,:))
            data_matrix = [xfft_r(ADD(1,M));xfft_r(ADD(2,M));xfft_r(ADD(3,M));xfft_r(ADD(4,M))];
            matrix2 = zeros(Base_2,Base_2);
            for T=1:Base_2
                matrix2(T,T) = W_mN(ADD(Base_2+1,M)*(T-1),4^(series+1));
            end
            matrix_r1 = matrix1*matrix2*data_matrix;
            xfft_r1(ADD(1,M)) = matrix_r1(1);
            xfft_r1(ADD(2,M)) = matrix_r1(2);
            xfft_r1(ADD(3,M)) = matrix_r1(3);
            xfft_r1(ADD(4,M)) = matrix_r1(4);
        end
    end
    %%
    data_out = xfft_r1;
end